Interleaving is used to help signal receivers overcome errors in acquired signals. For example, interleaving is applied to signals that are sent in wireless telecommunications networks that comply with the Third Generation Partnership Program (3GPP) standards.
Generally speaking, interleaving, as performed by an interleaver, is the deliberate and reversible disordering of a sequence of information symbols. If a receiver acquires an interleaved signal in which an error affects a contiguous group of symbols, the error can be dispersed by reversing the interleaving, so-called “deinterleaving.”
The ability to disperse an error is important when a transmitted information symbol sequence is prepared using forward error correction (FEC) coding that enables the resolution of an error in an acquired sequence provided that the error does not extend over too great a contiguous part of the acquired sequence. Turbo encoding is an example of FEC that is used within the 3GPP standards.
In a turbo encoder, a symbol sequence is supplied in parallel to both a first convolutional encoder and an interleaver. The interleaver produces an interleaved version of the sequence, which is then input to a second convolutional encoder. The outputs of the convolutional encoders are combined with the original sequence to provide the output of the turbo encoder. In a turbo decoder, a received turbo encoded sequence is used to prime a pair of constituent decoders. The output of a first one of the constituent decoders is interleaved and sent to the second constituent decoder for a further decoding iteration and the output of the second constituent decoder is deinterleaved and sent to the first constituent decoder for a further decoding iteration. The outputs of the first and second constituent decoders are exchanged several times prior to the emergence of a finally decoded sequence. Thus, where turbo coding is employed, considerable processing effort is devoted to interleaving, particularly in turbo decoding.
Several classes of interleaving algorithm exist. For example, a rectangular interleaver loads a symbol sequence into a memory block in a column-wise fashion and reads the symbols out in a row-wise fashion. Another type of interleaving is quadratic permutation polynomial (QPP) interleaving, which will be discussed after a brief reminder regarding some mathematical operations that feature in the remainder of this document:                the operation A mod B returns the remainder part of A divided by B.        the floor function/operation └C┘ returns the largest integer value that is less than C.        
Given a data sequence of length K symbols (where K has an integer value) and two parameters a and b that are dependent on K), the relationship between the position x of a symbol in the interleaved sequence and its position f(x) in the original sequence of QPP interleaving is:f(x)=(ax+bx2)mod K  Equation 1where x=0, 1, 2, 3, 4, . . . , K−1.
It has been shown in “A Decoder Architecture for High-Speed Free-Space Laser Communications” (M. Cheng, M. Nakashima, J. Hamkins, B. Moision, and M. Barsoum, Proceedings of SPIE, vol. 5712, pp. 174-185, April 2005) that if we define:g(x)=(a+b+2bx)mod Kthen:f(x+1)=(f(x)+g(x))mod Kandg(x+1)=(g(x)+2b)mod K
The function g(x) is an auxiliary function that recursively defines f(x).